1. Field of the Invention
The present invention generally relates to electronic circuits and, more specifically, to circuits executing RSA-type asymmetrical ciphering algorithms. The present invention more specifically relates to the protection, during the generation of prime numbers in an electronic circuit, against side channel attacks, for example, by statistical analysis of the power consumption of the circuit (SPA—simple power analysis) or of its electromagnetic signature, or against fault-injection attacks.
The present invention applies to any electronic circuit exploiting an algorithm exploiting a prime number factorization and, more specifically, to chip cards.
2. Discussion of the Related Art
The RSA algorithm is one of the most commonly used asymmetrical ciphering algorithms (with a public key). This algorithm is used to cipher/decipher data or to sign data and enable them to be authenticated. It is based on the use of a pair of keys comprising a public key and a private key. In ciphering/deciphering mode, the public key is used by a transmitter to cipher data to be confidentially communicated to a receiver, the latter using its private (or secret) key to decipher the data. For an authentication, the private key is used by the transmitter to sign the data while the public key is used by the receiver to authenticate the signature.
The public key is relatively widely accessible to enable the transmitter of the ciphered data or the receiver of the signed data to exploit these data. However, the private key is reserved to the circuit having created the pair of keys. The holder of the pair of keys may directly communicate the public key to the other party to enable it to process the data.
The generation of the pair of public and private keys requires the use of two different relatively prime numbers “p” and “q”, of relatively large size (typically, 1,024 or 2,048 bits). The product of these prime numbers represents encryption modulus “n”. Numbers p and q are selected so that numbers p−1 and q−1 are prime with a quantity “e”, called public exponent, the latter being then prime with the Euler indicator “φ(n)” of product n (φ(n)=(p−1)(q−1)). As a result, there exists an integer “d” such that product e*d is congruent to 1 modulo φ(n). Pair n and e represents the public key while pair n and d represents the private key. Private exponent d represents the inverse of exponent e, modulo (p−1)(q−1). Prime numbers p and q are only present in the circuit contained the private key.
The robustness of the RSA algorithm depends on prime numbers p and q. To “break” the RSA algorithms based on the public key, one needs to be able to factorize number n, and thus to obtain prime numbers p and q. Once this factorization is known, private exponent d can be calculated from public exponent e (d is obtained by calculating the inverse of e modulo (p−1)(q−1)). It is currently considered that by using modules n of sufficient size (typically on the order of 1,500 bits), current algorithms do not enable, within a reasonable time, to factorize number n.
However, the introduction of numbers p and q into the electronic circuit or their generation by this circuit is particularly critical in terms of security, since their discovery by a hacker at this time of the circuit life provides him with the factorization of number n.
A first technique for generating RSA keys comprises generating these keys outside of the electronic circuit. Quantities p and q are introduced into the electronic circuit in a customization phase. This technique is not responsive to fault injection attacks since the keys are not generated by the actual electronic circuit.
A second known technique comprises having the actual electronic circuit generate the prime numbers in a secure environment (in practice in a protected installation, with a reserved access). With this technique, attacks are not a problem either during the prime number generation.
However, more and more often, electronic circuits are desired to be able to generate their RSA keys outside of such secure environments. This, for example, enables regenerating new keys in the case where a previous key has been repudiated (key assumed to have been hacked). Such a generation is for example performed during a customization of the electronic circuit in a non-secure environment or during a first use (for example, for circuits used for signature calculations or electronic identifiers). According to an example of application to electronic passports, the key is desired to be generated by the electronic chip contained in the passport once it is in its holder's hands. Thus, this key cannot have been previously used in a passport authentication procedure.
Public exponent e may be a parameter of the public key infrastructure (PKI) and is the same for all keys. It is, for example, introduced into the electronic circuit during the manufacturing thereof (in a ROM) or during a customization phase (in an EEPROM).
Public exponent e may also be generated by the electronic circuit, for example, by selection of a random number, and may then be communicated to the elements with which it needs to communicate.
The public key (public exponent and encryption modulus) is thus either known by the receiver (signature) or by the transmitter (ciphering), or communicated thereto (for each transaction and once and for all) by the electronic circuit holding the private key. The public key further needs generally to be certified.
The generation of large prime numbers is costly in terms of time and calculation. In particular, so-called primality tests which enable to validate or not the prime character of a number generally implement modular exponentiations requiring a significant number of calculations (for example, the so-called Miller-Rabin primality test). This is why it is desired to only perform such tests for candidate numbers already having successfully passed tests with respect to relatively small prime numbers. Such tests correspond to divisions by relatively small prime numbers or to comparisons with respect to tables of prime numbers. For example, a Miller-Rabin test can be performed with a small base (two, for example) or a largest common divider calculation may be performed (for example, adding bytes modulo 255 to obtain a result smaller than 255 and then calculate the largest common divider of this result with 255—if it is different from 1, a single test can tell that the number is not dividable by the three factors of 255, that is, 3, 5, and 17).
When the prime numbers are generated by the electronic circuit in a non-secure environment, the circuit is capable of undergoing fault injection attacks (power supply disturbance, laser attacks, etc.) exploited by analysis of the inputs-outputs or of the circuit consumption, or to undergo side channel attacks (SPA or DPA, or electromagnetic analysis).
Another risk of the generation of prime numbers by the electronic circuit is an attack aiming a modifying the number finally selected. An attack at the end of a Miller-Rabin test may be used to modify the number taken into account by the algorithm. If one of numbers p or q is not prime, encryption modulus n is easier to factorize, which decreases the security of the RSA algorithm.